package com.lishem.leftgod.level1.class02;

/**
 * 字符串搜索算法
 */
public class Code_01_KMP {


    public static int getIndexOf(String s, String m) {
        if (s == null || m == null || s.length() < m.length()) {
            return -1;
        }
        char[] ss = s.toCharArray();
        char[] ms = m.toCharArray();
        int[] next = getNextArray(ms);
        int p1 = 0, p2 = 0;
        while (p1 != ss.length && p2 != ms.length) {
            if (ss[p1] == ms[p2]) {
                p1++;
                p2++;
            } else if (next[p2] != -1) {
                p2 = next[p2];
            } else {
                p1++;
            }
        }
        return p2 == ms.length ? p1 - p2 : -1;
    }

    private static int[] getNextArray(char[] ms) {
        if (ms.length == 1) {
            return new int[]{-1};
        }
        int[] next = new int[ms.length];
        next[0] = -1;
        next[1] = 0;
        int pos = 2;
        int cn = 0;
        while (pos != next.length) {
            if (ms[cn] == ms[pos - 1]) {
                next[pos++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[pos++] = 0;
            }
        }
        return next;
    }


    public static void main(String[] args) {
        String str = "abcabcababaccc";
        String match = "ababa";
        System.out.println(getIndexOf(str, match));
    }
}
